package com.leet.backtracking;

import java.util.*;

public class Zuhezonghe2 {

    //求和
    int sumTemp(List<Integer> tmp){
        int sum = 0;
        for(Integer i:tmp){
            sum += i;
        }
        return sum;
    }
    void backTracking(int[] candidates, int target,
                      List<Integer> tmp, boolean[] vis,List<List<Integer>> ans){
        //出口
        if(sumTemp(tmp) >= target){
            Collections.sort(tmp);
            if(sumTemp(tmp) == target && !ans.contains(tmp)){
                ans.add(new ArrayList<>(tmp));
            }
            return;
        }
        //回溯
        for(int i = 0;i < candidates.length;i++){
            if(!vis[i]){
                vis[i]=true;
                tmp.add(candidates[i]);
                backTracking(candidates, target, tmp, vis, ans);
                tmp.remove(tmp.size()-1);
                vis[i]=false;
            }
        }

    }
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        //准备素材
        List<Integer> tmp = new ArrayList<>();
        boolean[] vis = new boolean[candidates.length];
        List<List<Integer>> ans = new ArrayList<>();
        backTracking(candidates, target, tmp, vis, ans);
        return ans;
    }
}
